package 中等.模拟;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 有 n 位玩家在进行比赛，玩家编号依次为 0 到 n - 1 。
 * 给你一个长度为 n 的整数数组 skills 和一个 正 整数 k ，其中 skills[i]
 * 是第 i 位玩家的技能等级。skills 中所有整数 互不相同 。
 * 所有玩家从编号 0 到 n - 1 排成一列。
 * 比赛进行方式如下：
 * 队列中最前面两名玩家进行一场比赛，技能等级 更高 的玩家胜出。
 * 比赛后，获胜者保持在队列的开头，而失败者排到队列的末尾。
 * 这个比赛的赢家是 第一位连续 赢下 k 场比赛的玩家。
 * 请你返回这个比赛的赢家编号。
 *
 * @ https://leetcode.cn/problems/find-the-first-player-to-win-k-games-in-a-row/?envType=daily-question&envId=2024-10-24
 * @date 2024/10/24
 */
public class 找到连续赢K场比赛的第一位玩家_3175 {

    public static void main(String[] args) {

    }

    /**
     * 模拟+双端队列+贪心
     * 如果 k >= skills.length - 1 ，那么只有可能是技能等级最高的玩家
     */
    public int findWinningPlayer(int[] skills, int k) {

        int maxSkiller = -1, curSkill = skills[0];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < skills.length; i++) {
            deque.addLast(i);
            if (skills[i] >= curSkill) {
                curSkill = skills[i];
                maxSkiller = i;
            }
        }
        if (k >= skills.length - 1) {
            return maxSkiller;
        }

        int preWinner = -1, cnt = 0;
        while (true) {
            Integer player1 = deque.pollFirst();
            Integer player2 = deque.pollFirst();
            int curWinner = skills[player1] > skills[player2] ?
                    player1 : player2;
            int curLoser = skills[player1] > skills[player2] ?
                    player2 : player1;

            if (preWinner == curWinner) {
                cnt++;
            } else {
                preWinner = curWinner;
                cnt = 1;
            }
            deque.addFirst(curWinner);
            deque.addLast(curLoser);

            if (cnt >= k) {
                return curWinner;
            }
        }
    }

}
